Problem statement: zenit16ckd
Do kelu aj s tými grafmi
Počet bodov: 40, časový limit: 2000ms
“Ale ich dostaneme!” pomyslel si Jaro počas prípravy súťažných úloh Zenitu a zrecykloval úlohu z predošlého kola.
A hádajte čo? Tú úlohu práve čítate! Ale nie tak úplne. Táto úloha sa totiž bude zaoberať Fibonacciho grafmi, s ktorými ste sa mohli stretnúť už na krajskom kole. Tentoraz však budete mať úlohu o čosi ťažšiu. Bude nás zaujímať nielen, aká je najkratšia cesta medzi dvomi vrcholmi, ale taktiež, koľko rôznych najkratších ciest existuje.
Dve cesty budeme považovať za rôzne, pokiaľ sa postupnosti vrcholov, cez ktoré prechádzajú, na niektorom mieste líšia (napr. cesty \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) a \(1 \rightarrow 3 \rightarrow 2 \rightarrow 4\) sú rôzne).
Nakoniec si pripomenieme, ako sa Fibonacciho grafy konštruujú.
Ako prvý graf označíme graf obsahujúci jediný vrchol s číslom \(0\). Ako druhý označíme graf s dvomi spojenými vrcholmi s číslami \(0\) a \(1\). Každý ďalší graf skonštruujeme z predošlých dvoch. Konkrétne \(N\)-tý nasledovne:
Vezmeme \((N-1)\)-vý a \((N-2)\)-hý graf a vrcholy s rovnakým číslom spojíme hranou
K číslam vrcholov pochádzajúcich z \((N-2)\)-hého grafu pripočítame \((N-1)\)-vé Fibonacciho číslo (rozmyslite si, že týmto zaručíme, že pre každé číslo od \(0\) po \(F_N - 1\) budeme mať práve jeden vrchol s týmto číslom).
Príklad prvých \(5\) Fibonacciho grafov.
Pre potreby tejto úlohy určíme prvé dve Fibonacciho čísla nasledovne: \(F_1 = 1\) a \(F_2 = 2\).
Vstup a výstup
V prvom riadku vstupu dostanete číslo \(n\) \((1 \leq n \leq 500)\) označujúce, koľký Fibonacciho graf uvažujeme. V druhom riadku dostanete dve čísla \(a\ b\) \((0 \leq a,b < F_n)\), čísla vrcholov.
Na jediný riadok výstupu vypíšte dve čísla oddelené medzerou: Dĺžku najkratšej cesty a počet rôznych najkratších ciest medzi vrcholmi \(a\) a \(b\).
Pozor, medzivýsledky môžu byť pomerne veľké!
Príklad
Input:
5
7 4Output:
4 5Najkratšie cesty sú nasledovné: \[7 \rightarrow 2 \rightarrow 0 \rightarrow 3 \rightarrow 4\] \[7 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 4\] \[7 \rightarrow 5 \rightarrow 0 \rightarrow 3 \rightarrow 4\] \[7 \rightarrow 5 \rightarrow 0 \rightarrow 1 \rightarrow 4\] \[7 \rightarrow 5 \rightarrow 6 \rightarrow 1 \rightarrow 4\]
